#include <stdio.h>
#include <stdlib.h>

typedef int DataType;

typedef struct LNode
{
    DataType val;
    struct LNode* next;
}LNode;

void Push(LNode** head, DataType x)
{
    LNode* tmp = (LNode*)malloc(sizeof(LNode));
    if (tmp == NULL)
    {
        return;
    }
    tmp->next = NULL;
    tmp->val = x;
    if (*head == NULL)
    {
        *head = tmp;
    }
    else 
    {
        LNode* next = *head;
        while (next->next)
        {
            next = next->next;
        }
        next->next = tmp;
    }
}

void DestroyNode(LNode** head)
{
    LNode* next = (*head)->next;
    while (next)
    {
        free(*head);
        *head = next;
        next = next->next;
    }
    free(*head);
}

void Print(LNode* head)
{
    while (head)
    {
        printf("%d ", head->val);
        head = head->next;
    }
}

int com_int(const void* q1, const void* q2)
{
    return (*(int*)q1 - *(int*)q2);
}

void sort(LNode** head)
{
    LNode* cur = *head;
    LNode* tmp = NULL;
    int arr[20];
    int i = 0;
    while (cur)
    {
        arr[i] = cur->val;
        ++i;
        cur = cur->next;
    }
    qsort(arr, i, sizeof(arr[0]), com_int);
    for (int j = 0; j < i; j++)
    {
        Push(&tmp, arr[j]);
    }
    free(*head);
    *head = NULL;
    *head = tmp;
}

void interSect(LNode* head1, LNode* head2)
{
    LNode* cur1 = head1;
    LNode* cur2 = head2;
    int arr[20];
    int i = 0;
    while (cur1)
    {
        while (cur2)
        {
            if (cur1->val == cur2->val)
            {
                arr[i] = cur1->val;
                ++i;
            }
            cur2 = cur2->next;
        }
        cur1 = cur1->next;
        cur2 = head2;
    }
    for (int j = 0; j < i; j++)
    {
        printf("%d ", arr[j]);
    }
    printf("\n");
}

void subs(LNode* head1, LNode* head2)
{
    LNode* cur1 = head1;
    LNode* cur2 = head2;
    int arr1[20];
    int arr2[20];
    int i = 0, j = 0;
    while (cur1)
    {
        while (cur2)
        {
            if (cur1->val == cur2->val)
            {
                arr1[i] = cur1->val;
                ++i;
            }
            cur2 = cur2->next;
        }
        cur1 = cur1->next;
        cur2 = head2;
    }
    cur1 = head1;
    int k = 0;
    while (cur1)
    {
        int flag = 1;
        for (j = 0; j < i; j++)
        {
            if (cur1->val == arr1[j])
            {
                flag = 0;
                break;
            }
        }
        if (flag == 1)
        {
            arr2[k] = cur1->val;
            ++k;
        }
        cur1 = cur1->next;
    }
    for (i = 0; i < k; i++)
    {
        printf("%d ", arr2[i]);
    }
    printf("\n");
}

int main() {
    LNode* L1 = NULL;

    int a1[] = { 1,2,7,5 };
    for (int i = 0; i < sizeof(a1) / sizeof(a1[0]); i++)
    {
        Push(&L1, a1[i]);
    }
   

    LNode* L2 = NULL;
    int a2[] = { 8,7,6,5 };
    for (int i = 0; i < sizeof(a2) / sizeof(a2[0]); i++)
    {
        Push(&L2, a2[i]);
    }
   

    LNode* L3 = NULL;
    LNode* next1 = L1;
    LNode* next2 = L2;

    while (next1)
    {
        Push(&L3, next1->val);
        next1 = next1->next;
    }
    while (next2)
    {
        Push(&L3, next2->val);
        next2 = next2->next;
    }

   /* sort(&L3);
    LNode* t = L3;
    while (t)
    {
        printf("%d ", t->val);
        t = t->next;
    }*/

    //interSect(L1, L2);

    subs(L1, L2);

    DestroyNode(&L1);
    DestroyNode(&L2);
    DestroyNode(&L3);


    return 0;
}